package com.meterhuang;

import lombok.extern.slf4j.Slf4j;

/**
 * 最大连续子序列和
 *
 * @author meterhuang
 * @date 2021/05/07 17:43
 */
@Slf4j
public class MaxSubArray {

	public static void main(String[] args) {
		int max = maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
		log.info("max:{}", max);
		max = maxSubArrayV2(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
		log.info("greed max:{}", max);
	}

	/**
	 *  f(i)=max{f(i−1)+nums[i],nums[i]}
	 * @param nums
	 * @return
	 */
	public static int maxSubArray(int[] nums) {
		int pre = 0, max = nums[0];
		for (int num : nums) {
			pre = Math.max(pre + num, num);
			max = Math.max(max, pre);
		}

		return max;
	}

	/**
	 * 贪心算法
	 * @param nums
	 * @return
	 */
	public static int maxSubArrayV2(int[] nums) {
		int ansNum = nums[0], s = 0;
		for (int num : nums) {
			s += num;
			if (s > ansNum) {
				ansNum = s;
			}
			// 如果小于0重新计数
			if (s < 0) {
				s = 0;
			}
		}

		return ansNum;
	}
}
